﻿// Hashtable.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <stdio.h>
#include "head.h"
#include "MinStack.h"
#include "MyQueue.h"
#include "isPalindrome.h"
#include <memory>

int main()
{
    std::cout << "Hello World!\n";

#pragma region 智能指针
    auto_ptr<string> ps;
    unique_ptr<string> ups;
    shared_ptr<string> sps;
#pragma endregion

#pragma region 20210121
    //13罗马字符转换
    /*
    int ret = romanToInt("MCMXCVI");
    cout << ret << endl;
    */

    //14. 最长公共前缀
    /*
    vector<string> strs;
    strs.push_back("flower");
    strs.push_back("aflow");
    strs.push_back("flight");
    string ret = longestCommonPrefix(strs); 
    cout << ret << endl;
    */

    //20. 有效的括号
    /*
    string st = "([)]";
    bool bRet = isValid(st);
    */

    //21. 合并两个有序链表
    /*
    ListNode l1(5), l11(6), l12(7);
    ListNode l2(11), l21(13), l22(14);
    l1.next = &l11;
    l11.next = &l12;
    l2.next = &l21;
    l21.next = &l22;

    ListNode *pRet = mergeTwoLists(&l1, &l2);
    */

    //26. 删除排序数组中的重复项
    /*
    vector<int> nums = { 1,1, 2, 3, 4,4 ,5};
    int ret = removeDuplicates(nums);
    */
    
    //27. 移除元素
    /*
    vector<int> nums = { 1,1, 2, 3, 4,1,4 ,5,1 };
    int ret = removeElement(nums, 1);
    */

    //28. 实现 strStr()
    /*
    string haystack = "cab", needle = "ab";
    int ret = strStr(haystack, needle);
    */

    //35. 搜索插入位置
    /*
    vector<int> nums = { 1,3,5,6 };
    int target = 0;
    int ret = searchInsert(nums, target);
    */

    //38. 外观数列
    /*
    string ret = countAndSay(5);
    */
#pragma endregion

#pragma region 20210122
    //53. 最大子序和
    /*
    vector<int> nums{-1,2,-7,20,0,5,-5,3,7};
    int ret = maxSubArray(nums);
    */

    //58. 最后一个单词的长度
    /*
    string str = "   ";
    int ret = lengthOfLastWord(str);
    */

    //66. 加一
    /*
    vector<int> src = {0,0,9,9,9 }, out;
    out = plusOne(src);
    */

    //67. 二进制求和
    /*
    string a = "1010";
    string b = "10";
    string strRet  =addBinary(a,b);
    */

    //69. x 的平方根
    /*
    int x = 150;
    int ret = mySqrt(x);
    */

    //70. 爬楼梯
    /*
    int n = 10;
    int ret = climbStairs(n);
    */

    //83. 删除排序链表中的重复元素
    /*
    ListNode l1(5), l11(6), l12(7),l13(7),l14(7),l15(9);
    l1.next = &l11;
    l11.next = &l12;
    l12.next = &l13;
    l13.next = &l14;
    l14.next = &l15;
    ListNode* pRet = deleteDuplicates(&l1);
    */

    //88. 合并两个有序数组
    /*
    vector<int> nums1 = { 1,2,5,6,9,10 };
    vector<int> nums2 = {};
    merge(nums1, 6, nums2, 0);
    */
    
    //100. 相同的树
    /*
    TreeNode* p = new TreeNode(1), * pl1 = new TreeNode(2), * pr1 = new TreeNode(3);
    p->left = pl1;
    p->right = pr1;
    TreeNode *q = new TreeNode(1),*ql1 = new TreeNode(2), *ql2 = new TreeNode(3);
    q->left = ql1;
    ql1->left = ql2;

    bool bRet = isSameTree(p, q);
    */

    //101. 对称二叉树
    /*
    TreeNode* root;
    bool ret = isSymmetric(root);
    */

    //104. 二叉树的最大深度
    /*
    TreeNode root(1), l1(1), l2(2), l3(3), l4(4), l5(5), l6(6);
    root.left = &l1;
    root.right = &l2;
    l1.left = &l3;
    l1.right = &l4;
    l4.left = &l6;
    l2.left = &l5;
    int ret = maxDepth(&root);
    */
#pragma endregion

#pragma region 20210123
    //107. 二叉树的层序遍历 II
    /*
    TreeNode root(0), l1(1), l2(2), l3(3), l4(4), l5(5);
    root.left = &l1;
    root.right = &l2;
    l1.left = &l3;
    l3.right = &l4;
    l2.left = &l5;
    vector<vector<int>> out =  levelOrderBottom(&root);
    */

    //108. 将有序数组转换为二叉搜索树
    /*
    vector<int> nums = { -10,-3,0,5,9 };
    TreeNode* ret = sortedArrayToBST(nums);
    */

    //110. 平衡二叉树
    /*
    TreeNode root(0),l1(1),l2(2),l3(3),l4(4),l5(5),l6(6);
    root.left = &l1;
    root.right = &l2;
    l1.left = &l3;
    l1.right = &l4;
    l2.left = &l5;
    l2.right = &l6;
    bool bRet = isBalanced(&root);
    */

    //111. 二叉树的最小深度
    /*
    TreeNode root(0), l1(1), l2(2), l3(3), l4(4), l5(5), l6(6);
    root.left = &l1;
    root.right = &l2;
    l1.left = &l3;
    l1.right = &l4;
    l2.left = &l5;
    l5.right = &l6;
    int ret = minDepth(&root);
    */

    //112. 路径总和
    /*
    TreeNode root(0), l1(1), l2(2), l3(3), l4(4), l5(5), l6(6);
    root.left = &l1;
    root.right = &l2;
    l1.left = &l3;
    l1.right = &l4;
    l2.left = &l5;
    l5.right = &l6;
    bool ret = hasPathSum(&root,10);
    */

    //118. 杨辉三角 
    /*
    int numRows = 5;
    vector<vector<int>> ret = generate(numRows);
    */

    //119. 杨辉三角 II
    /*
    int rowIndex = 3;
    vector<int> out = getRow(rowIndex);
    */

    //121. 买卖股票的最佳时机    
    /*
    vector<int> prices = { 17,1,5,3,6,4 };
    int ret = maxProfit(prices);
    */

    //125. 验证回文串
    /*
    string s = "A man, a plwewe: Panama";
    bool ret = isPalindrome(s);
    */

    //141. 环形链表
    /*
    ListNode head(3),l1(2),l2(0),l3(4);
    head.next = &l1;
    l1.next = &l2;
    l2.next = &l3;
    l3.next = &l1;
    bool ret = hasCycle(&head);
    */
#pragma endregion

#pragma region 20210126
    //155. 最小栈
/*
    MinStack minStack;
    minStack.push(2147483646);
    minStack.push(2147483646);
    minStack.push(2147483647);
    cout << minStack.top() << endl;
    minStack.pop();
    cout << minStack.getMin() << endl;   
    minStack.pop();
    cout << minStack.getMin() << endl;  // -- > 返回 - 2
    minStack.pop();
    minStack.push(2147483647);
    cout << minStack.top() << endl;
    cout << minStack.getMin() << endl;  // -- > 返回 - 2
    minStack.push(-2147483648);
    cout << minStack.top() << endl;      //-- > 返回 0.
    cout << minStack.getMin() << endl;
    minStack.pop();
    cout << minStack.getMin() << endl;  // -- > 返回 - 2
*/
    //160. 相交链表
    /*
    ListNode a1(4), a2(6), a3(1), a4(8), a5(4);
    ListNode b1(11), b2(1);
    a1.next = &a2;
    a2.next = &a3;
    a3.next = &a4;
    a4.next = &a5;
    b1.next = &b2;
    b2.next = &a4;
    ListNode* ret = getIntersectionNode(&a1, &b1);
    */
    
    //167. 两数之和 II - 输入有序数组
    /*
    vector<int> src = { 1,2,3,4,5,8,11 };
    vector<int> ret = twoSumII(src, 11);
    */

    //168. Excel表列名称
    /*
    string  ret = convertToTitle(52);    
    cout << ret << endl;
    */

    //169. 多数元素
    /*  
    vector<int> nums = { 2,3,3,2,4,3,3 };
    int ret = majorityElement(nums);
    */
#pragma endregion

#pragma region 20210127
    //171. Excel表列序号
    /*
    string s = "AB";
    int ret = titleToNumber(s);
    */

    //172. 阶乘后的零
    //int ret = trailingZeroes(10);

    //190. 颠倒二进制位
    //uint32_t ret = reverseBits((uint32_t)10);

    //202. 快乐数
    //bool ret = isHappy(9);

    //203. 移除链表元素
    /*
    ListNode n1(1), n2(2), n3(3), n4(4), n5(5), n6(6);
    n1.next = &n2;
    n2.next = &n3;
    n3.next = &n4;
    n4.next = &n5;
    n5.next = &n6;
    ListNode* ret = removeElements(&n1,6);
    */

    //204. 计数质数
    //int ret = countPrimes(10);

    //204. 计数质数
    //int ret = countPrimes(20);

    //205. 同构字符串
    //bool ret = isIsomorphic("eggabcd","addbcde");

    //206. 反转链表
    /*
    ListNode n1(1), n2(2), n3(3), n4(4), n5(5), n6(6);
    n1.next = &n2;
    n2.next = &n3;
    n3.next = &n4;
    n4.next = &n5;
    n5.next = &n6;
    ListNode* head = reverseList(&n1);
    */

    //217. 存在重复元素
    //vector<int> nums;
   // bool ret = containsDuplicate(nums);

    //219. 存在重复元素 II
    //vector<int> nums ={ 1,2,3,4,1 };
    //bool ret = containsNearbyDuplicate(nums, 3);

    //226. 翻转二叉树
    //TreeNode root(0);
    //TreeNode* ret = invertTree(&root);

    //228. 汇总区间
    //vector<int> nums = { -2,-1,0,2,4,8,9 };
    //vector<string> ret = summaryRanges(nums);

    //231. 2的幂
    //bool ret = isPowerOfTwo(1024);

    //232. 用栈实现队列
    /*
    MyQueue myQue;
    myQue.push(1);
    myQue.push(2);
    myQue.push(3);
    myQue.push(4);
    cout << myQue.peek() << endl;
    cout << myQue.pop() << endl;
    cout << myQue.pop() << endl;
    cout << myQue.peek() << endl;
    cout << myQue.empty() << endl;
    */
    
    //234. 回文链表
    /*
    ListNode n1(0),n2(1),n3(0);
    n1.next = &n2;
    n2.next = &n3;
    bool ret = isPalindrome(&n1);
    Solution s;
    s.isPalindrome(&n1);
    */

    //235. 二叉搜索树的最近公共祖先
    /*
    TreeNode root(6),n2(2),n0(0),n4(4),n3(3),n5(5),n7(7),n8(8),n9(9);
    root.left = &n2;
    root.right = &n8;
    n2.left = &n0;
    n2.right = &n4;
    n4.left = &n3;
    n4.right = &n5;
    n8.left = &n7;
    n8.right = &n9;
    TreeNode* ret = lowestCommonAncestor(&root,&n2,&root);
    */

    //237. 删除链表中的节点
    /*
    ListNode n1(0), n2(1), n3(0);
    n1.next = &n2;
    n2.next = &n3;
    deleteNode(&n2);
    */
#pragma endregion




int a = 0;
}




// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
